﻿#define _CRT_SECURE_NO_WARNINGS 1

/*
快速排序递归/非递归（hoare，挖坑法，前后指针）
博客链接：https://blog.csdn.net/m0_63020222/article/details/124049805
重点学习
*/

#include<stdio.h>
#include"Stack.h"

void QuickSort(int* array, int left, int right);//快速排序
int  PartSort1(int* array, int left, int right);//快速排序hoare版
int  PartSort2(int* array, int left, int right);//快速排序挖坑法
int  PartSort3(int* array, int left, int right);//快速排序前后指针版

int GetMiddleIndex(int* array, int left, int right);//三位取中法(选取元素大小相对靠中的为基准值)
void QuickSortNonR(int* array, int size);//快速排序非递归版

void InsertSort(int* array, int size);//直接插入排序
void PrintArray(int* array, int size);//数组打印
void Swap(int* num1, int* num2);//整数交换

void TestPartSort();//快速排序测试函数

int main() {
	TestPartSort();
	return 0;
}

void QuickSort(int* array, int left, int right) {//快速排序
	if (right - left <= 16) {//阈值设置为16
		InsertSort(array + left, right - left);//达到阈值，进行直接插入排序
	}
	else {
		if (right - left <= 1) {//区间内少于等于1个元素，不需要再排
			return;
		}
		int div = PartSort2(array, left, right);//找一个基准值对区间元素进行划分，分割完成后返回基准值位置
		QuickSort(array, left, div);//对基准值左侧进行快排
		QuickSort(array, div + 1, right);//对基准值右侧进行快排
	}
}

int PartSort1(int* array, int left, int right) {//快速排序hoare版
	int begin = left;
	int end = right - 1;
	int midPos = GetMiddleIndex(array, left, right);//获取元素大小相对靠中的元素下标
	if (midPos != end) {//将该元素交换到末尾，从而不影响后续代码的逻辑实现
		Swap(&array[midPos], &array[end]);
	}
	int key = array[end];//取最后一个元素为基准值
	while (begin < end) {//begin与end没有相遇
		while (begin < end && array[begin] <= key) {//1.从前往后找比基准值key大的元素
			begin++;
		}
		while (begin < end && array[end] >= key) {//2.从后往前找比基准值key小的元素
			end--;
		}
		if (begin != end) {//3.交换两个元素
			Swap(&array[begin], &array[end]);
		}
	}
	Swap(&array[begin], &array[right - 1]);//4.将基准值交换到区间中间位置
	return begin;//5.返回基准值下标
}

int PartSort2(int* array, int left, int right) {//快速排序挖坑法
	int begin = left;
	int end = right - 1;
	int midPos = GetMiddleIndex(array, left, right);//获取元素大小相对靠中的元素下标
	if (midPos != end) {//将该元素交换到末尾，从而不影响后续代码的逻辑实现
		Swap(&array[midPos], &array[end]);
	}
	int key = array[end];//1.取最后一个元素为基准值，并挖坑end
	while (begin < end) {//begin与end没有相遇
		while (begin < end && array[begin] <= key) {//2.从前往后找比基准值key大的元素
			begin++;
		}
		if (begin != end) {
			array[end--] = array[begin];//3.填end坑,挖begin坑,end前移一位
		}
		while (begin < end && array[end] >= key) {//4.从后往前找比基准值key小的元素
			end--;
		}
		if (begin != end) {
			array[begin++] = array[end];//5.填begin坑，挖end坑，begin后移一位
		}
	}
	array[end] = key;//6.基准值放入最后一个坑内
	return end;//7.返回基准值下标
}

int PartSort3(int* array, int left, int right) {//快速排序前后指针版
	int cur = left;//标记第一个元素
	int prev = cur - 1;//位于cur之后一个位置
	int midPos = GetMiddleIndex(array, left, right);//获取元素大小相对靠中的元素下标
	if (midPos != right - 1) {//将该元素交换到末尾，从而不影响后续代码的逻辑实现
		Swap(&array[midPos], &array[right - 1]);
	}
	int key = array[right - 1];//取最后一个元素为基准值
	while (cur < right) {
		if (array[cur] < key && ++prev != cur) {//始终保存cur与prev之间的元素都大于基准值key
			Swap(&array[cur], &array[prev]);
		}
		cur++;
	}
	if (++prev != right - 1) {//将基准值交换到prev的下一个位置
		Swap(&array[right - 1], &array[prev]);
	}
	return prev;
}

void QuickSortNonR(int* array, int size) {//快速排序非递归版
	Stack s;
	StackInit(&s);
	int left = 0;
	int right = size;

	StackPush(&s, right);//依次压入右边界和左边界
	StackPush(&s, left);

	while (!StackEmpty(&s)) {//栈不为空，循环进行
		left = StackTop(&s);//获取栈顶，左边界
		StackPop(&s);//左边界出栈
		right = StackTop(&s);//获取栈顶，右边界
		StackPop(&s);//右边界出栈

		if (right - left <= 16) {//子序列达到阈值
			InsertSort(array + left, right - left);//进行直接插入排序
		}
		else {
			int div = PartSort2(array, left, right);
			//基准值左侧（left，div）；右侧（div+1，right）

			//先压右侧子序列边界（先压右边界，再压左边界）
			StackPush(&s, right);
			StackPush(&s, div + 1);

			//再压左侧子序列边界
			StackPush(&s, div);
			StackPush(&s, left);
		}
	}
}

int GetMiddleIndex(int* array, int left, int right) {//三位取中法(选取元素大小相对靠中的为基准值)
	int mid = (left + right) / 2;
	//返回基准值的下标
	if (array[left] < array[right - 1]) {
		if (array[mid] < array[left]) {
			return left;
		}
		else if (array[mid] > array[right - 1]) {
			return right - 1;
		}
		else {
			return mid;
		}
	}
	else {//array[left]>=array[right-1]
		if (array[mid] > array[left]) {
			return left;
		}
		else if (array[mid] < array[right - 1]) {
			return right - 1;
		}
		else {
			return mid;
		}
	}
}

void InsertSort(int* array, int size) {//直接插入排序
	for (int i = 1; i < size; i++) {//从1开始循环，默认数组内第一个元素为有序序列
		int end = i - 1;//标记已排序序列最后位置下标
		int key = array[i];//依次拿取数组内元素
		while (end >= 0 && key < array[end]) {//key从前往后比较：小于当前元素，继续往前走
			array[end + 1] = array[end];//将当前元素往后移一个位置
			end--;
		}
		array[end + 1] = key;//key大于等于当前元素，插入到当前位置之后
	}
}

void PrintArray(int* array, int size) {//数组打印
	for (int i = 0; i < size; i++) {
		printf("%d ", array[i]);
	}
}

void Swap(int* num1, int* num2) {//整数交换
	int temp = *num1;
	*num1 = *num2;
	*num2 = temp;
}

void TestPartSort() {//快速排序测试函数
	int array[] = { 5,4,8,1,9,7,3,2,6,0 };
	int length = sizeof(array) / sizeof(array[0]);

	printf("排序前：");
	PrintArray(array, length);
	//QuickSort(array, 0, length);//递归方式
	QuickSortNonR(array, length);//非递归方式
	printf("\n排序后：");
	PrintArray(array, length);
}